package com.example.lettcode._202411._20241116;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
350. 两个数组的交集 II
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。
返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

该题目与349有差异的是需要返回最少的那个相同的次数，
在349中：nums1 = [1,2,2,1], nums2 = [2,2] 只需要返回[2]
 */
public class _01_liang_ge_shu_zu_jiao_ji_2 {

    public static void main(String[] args) {

    }

    public static int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> list1 = new ArrayList<>();

        for (int num1 : nums1) {
            list1.add(num1);
        }

        List<Integer> ret = new ArrayList<>();
        for (int num2 : nums2) {
            if(list1.contains(num2)) {
                ret.add(num2);
                list1.remove(Integer.valueOf(num2));
            }
        }

        return ret.stream().mapToInt(Integer::valueOf).toArray();
    }


    public static int[] intersect2(int[] nums1, int[] nums2) {
        int num2 = 0;

        Arrays.sort(nums1);
        Arrays.sort(nums2);

        List<Integer> ret = new ArrayList<>();
        for (int i = 0; i < nums1.length; i++) {
            int num1 = nums1[i];
            for (int j = num2; j < nums2.length; j++) {
                if (nums2[j] == num1) {
                    num2 = j+1;
                    ret.add(num1);
                    break;
                }
            }
        }
        return ret.stream().mapToInt(Integer::valueOf).toArray();
    }

    /*
    提示：
    1 <= nums1.length, nums2.length <= 1000
    0 <= nums1[i], nums2[i] <= 1000
     */
    public static int[] intersect3(int[] nums1, int[] nums2) {
        int[] temps = new int[1000];

        for (int num1 : nums1) {
            temps[num1] += 1;
        }

        int min = Math.min(nums1.length, nums2.length);
        int[] ret = new int[min];
        int index = 0;
        for (int num2 : nums2) {
            if (temps[num2] > 0) {
                ret[index++] = num2;
                temps[num2] -= 1;
            }
        }

        return Arrays.copyOf(ret, index);
    }
}
